package junior.DynamicProgramming动态规划;

public class 最长上升子串 {

    public static void main(String[] args) {
        int n = 5;  //数字个数
        int[] a = {0,1,5,3,4,2};  //数字（边界控制）
        int[] b = new int[n+1];   //逆推，存储最优解
        int[] c = new int[n+1];   //测试专用，保存longmax的变化过程（默认最大下标为0）
        int submax = 0;  //存储序列子结构的最优解，且为最优解的最大值
        int longmax = 0;  //用于输出结果，存储序列的最优解变量（最长上升子串），边界控制，起始位0
        b[n] = 1;  //逆推，控制边界，从最大下标开始，默认最优解为1，即最有一个元素
//        状态转移方程（核心数组是b，）
        for (int i = n-1; i >=1; i--) {  //从最大下标的后一位开始遍历
            submax=0;
            for (int j = i+1; j <=n; j++) {  //这个for循化，找出当前i位置后面的子序列的最优解，赋给submax，若无，这为初试值0；
                if (a[i] <= a[j] && b[j] >submax) //这里的<=，看情况，即上升是否可以存在相同数字
                    submax = b[j];
            }
            b[i] = submax + 1;  //更新i位置的最优解
            if (b[i] > longmax)
                longmax = b[i];  //更新序列最优解
            c[i] = longmax;
        }
//        输出最长上升序列的长度
        System.out.println("最长上升序列长度:"+longmax);
//        输出数组信息
        System.out.print("输出数组原始信息:");
        for (int i = 1; i < n + 1; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
//        输出状态转移数组信息
        System.out.print("状态转移数组信息:");
        for (int i = 1; i < n + 1; i++) {
            System.out.print(b[i]+" ");
        }
        System.out.println();
//        输出序列最优解变化过程(逆推,从右向左看)
        System.out.print("最优解的变化过程:");
        for (int i = 1; i < n + 1; i++) {
            System.out.print(c[i]+" ");
        }
        System.out.println();
//        输出最大上升子序列
        System.out.print("最大的上升子序列:");
        int x = longmax;
        for (int i = 1; i <n+1 ; i++) {
            if (b[i] == x){
                System.out.print(a[i]+" ");
                x--;
            }
        }
    }
}
